/**
*给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
*给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母
*
*/


#include <iostream>
#include <string>
#include <map>
#include <vector>

using namespace std;

class phonenumber
{
public:
    vector<string> lettercombinations(string digits)
    {
        vector<string> combinations; //记录表
        if(digits.empty())
        {
            return combinations;
        }
        
        map<char, string> phonemap{{'2', "abc"},{'3', "def"},{'4', "ghi"},{'5', "jkl"},
                                    {'6', "mno"},{'7', "pqrs"},{'8', "tuv"},{'9', "wxyz"}};
        
        string combination; //组合temp
        backtrack(combinations,phonemap,digits,0,combination);
        return combinations;
    }
    
    void backtrack(vector<string>& combinations,const map<char,string> phonemap,const string& digits,
                   int index, string& combination)
    {
        if(index==digits.length())  //length比index多1；
        {
            combinations.push_back(combination);
        }
        else
        {
            char digit=digits[index];
            const string& letters=phonemap.at(digit);
            for(const char& letter: letters) //将letters中的元素循环完
            {
                combination.push_back(letter);
                backtrack(combinations,phonemap,digits,index+1,combination);
                combination.pop_back();
            }
        }
    }
};

int main()
{
    class phonenumber a;
    vector<string> aa=a.lettercombinations("235");
    
    for(int i=0;i<aa.size();++i)
    {
        cout<<aa[i]<<endl;
    }
    return 0;
}
    

